The present invention concerns sequencing of data in a multi-node communications network, in particular a data sequencing method to improve transmission of self-similar data through the network and reduce buffer expenditures within the network.
Broadband local area network (LAN) traffic, bursty variable bit-rate (VBR) video traffic and wide-area network (WAN) traffic, such as on the Internet, have been shown to have self-similar, fractal, properties. Self-similar traffic behaves very differently than voice traffic or traffic predicted by packet traffic models, which typically conform to Poisson-like distributions. In a Poisson-like packet traffic model, aggregate traffic become smoother (i.e. less prone to bursts of data) as the number of traffic sources increases. The self-similar nature of LAN and VBR video traffic, on the other hand, cause such traffic to manifest a self-similar burstiness at every time scale. Bursts, consisting of bursty sub-periods separated by less bursty sub-periods, are seen in the traffic on a millisecond time scale, as well as on an hour time scale. This self-similar, fractal, pattern imparts a long-range dependence (LRD) in the traffic. The burstiness of the composite of such traffic tends to increase, rather than decrease, as the number of traffic sources increase.
Self-similar burstiness may lead to a reduction in network performance. Transmission nodes within the network can only handle a certain data rate, which is often exceeded at the height of a burst, leading to congestion and data loss. One solution is to reduce the amount data travelling through the network, thus decreasing the overflow frequency of bursts. This is not a desirable solution, however, as it results in the underutilization of network resources. Merely increasing the buffer size in the network may not relieve the problem as the burstiness of the data exhibits itself on several time scales. Greater buffer size may, however, increase the delay for traffic passing through the network.
Networks that may be affected by long range dependency include broadband ISDN networks and Internet networks. This effect of long-range dependency is discussed in an article by W. Leland et al. entitled “On the Self-Similar Nature of Ethernet Traffic,” Proc. ACMSigcomm '93, San Francisco, 1993, pp. 183–193 and in an article by A. Erramili et al. entitled “Experimental Queuing Analysis with Long-Range Dependent Packet Traffic,” IEEE/ACM Transactions on Networking vol. 4, no. 2, 1996.
One solution for handling data that exhibits long range dependency is to incorporate a queuing buffer at the source node to store excess data during bursts for later transmission during intervening lower traffic periods, effectively smoothing the data bursts. This method is presently in use, especially for VBR video data. As data comes into a transmission node, it enters the back of the queuing buffer. Meanwhile, the oldest data in the queuing buffer is taken off of the front of the buffer at a predetermined rate and transmitted. The remaining data in the buffer is moved forward. This system smoothes the data traffic across transmission nodes and allows the network to operate at is a high efficiency if the full bandwidth of the network can be filled with similar fixed-bandwidth components. The amount of data waiting in the buffer fluctuates with the incoming traffic level, absorbing the burstiness of the stream. To effectively handle LRD data (i.e. maintaining a low cell loss rate), the smoothing buffer must be large. Larger buffers, however, cause increased delay that may not be acceptable for some applications.